package demo_0713;

import java.util.Arrays;

/**
 * 基于数组实现的大根堆（优先级队列）
 */
public class PriorityQueue_T2_0330 {
    public int[] elem;      // 存储堆元素的数组
    public int usedSize;    // 堆中当前元素的个数

    /**
     * 构造函数，初始化堆数组大小为10
     */
    public PriorityQueue_T2_0330() {
        elem = new int[10];
    }

    /**
     * 根据给定数组创建大根堆
     * @param array 用于创建堆的输入数组
     * 时间复杂度：O(n)
     */
    public void createHeap(int[] array) {
        // 将数组元素逐个放入堆中
        for (int i = 0; i < array.length; i++) {
            if (isFull()) {
                bigheap();  // 如果堆已满，进行扩容
            }
            elem[usedSize++] = array[i];
        }
        // 从最后一个非叶子节点开始向下调整
        for (int i = (usedSize - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(i, usedSize);
        }
    }

    /**
     * 向下调整（堆化）
     * @param root 当前子树的根节点下标
     * @param len  堆的当前大小
     * 时间复杂度：O(logn)
     */
    private void shiftDown(int root, int len) {
        int child = root * 2 + 1;  // 左孩子下标
        while (child < usedSize) {
            // 如果有右孩子且右孩子比左孩子大，选择右孩子
            if(child + 1 < usedSize && elem[child] < elem[child + 1]) {
                child++;
            }
            // 如果孩子比父节点大，交换它们
            if (elem[child] > elem[root]) {
                swap(child, root);
                root = child;
                child = root * 2 + 1;
            } else {
                break;  // 调整完成
            }
        }
    }

    /**
     * 向堆中插入元素
     * @param val 要插入的值
     */
    public void push(int val) {
        if (isFull()) {
            bigheap();  // 堆满时扩容
        }
        elem[usedSize] = val;  // 将新元素放在数组末尾
        shiftUp(usedSize);     // 向上调整
        usedSize++;            // 堆大小增加
    }

    /**
     * 向上调整（堆化）
     * @param child 新插入元素的下标
     */
    private void shiftUp(int child) {
        for(int parent = (child - 1) / 2; parent >= 0;) {
            if (elem[child] > elem[parent]) {
                swap(child, parent);  // 如果子节点比父节点大，交换它们
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;  // 调整完成
            }
        }
    }

    /**
     * 检查堆是否已满
     * @return 如果堆已满返回true，否则返回false
     */
    public boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 删除堆顶元素（优先级最高的元素）
     */
    public void pollHeap() {
        if (isEmpty()) return;  // 堆为空直接返回
        swap(0, usedSize - 1);  // 将堆顶元素与最后一个元素交换
        usedSize--;             // 堆大小减1
        shiftDown(0, usedSize); // 从新的堆顶开始向下调整
    }

    /**
     * 检查堆是否为空
     * @return 如果堆为空返回true，否则返回false
     */
    public boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     * 获取堆顶元素（优先级最高的元素）
     * @return 堆顶元素的值，如果堆为空返回-1
     */
    public int peekHeap() {
        if (isEmpty()) return -1;
        return elem[0];
    }
    /**
     * 堆扩容方法（容量翻倍）
     */
    //扩容
    private void bigheap() {
        elem = Arrays.copyOf(elem,elem.length * 2);
    }
    /**
     * 交换数组中两个元素的位置
     * @param a 第一个元素的下标
     * @param b 第二个元素的下标
     */
    //交换
    private void swap(int a, int b) {
        int tmp = elem[a];
        elem[a] = elem[b];
        elem[b] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
        PriorityQueue_T2_0330 priorityQueue = new PriorityQueue_T2_0330();
        priorityQueue.createHeap(array);
        System.out.println("堆顶元素：" + priorityQueue.peekHeap());
        priorityQueue.push(10);
        System.out.println("堆顶元素：" + priorityQueue.peekHeap());
        priorityQueue.pollHeap();
        System.out.println("堆顶元素：" + priorityQueue.peekHeap());
        System.out.println("堆是否为空：" + priorityQueue.isEmpty());
        System.out.println("堆的大小：" + priorityQueue.usedSize);
        System.out.print("堆中的元素：");
        for (int i = 0; i < priorityQueue.usedSize; i++) {
            System.out.print(priorityQueue.elem[i] + " ");
        }
        System.out.println();
        System.out.println("------------------------");
    }
}
